package nowcoder;

import java.util.Scanner;

/**
 * KY11 二叉树遍历
 * https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
 */
public class 二叉树遍历 {
    public static class TreeNode{//定义二叉树这个类
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }

        public TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static int index = 0;
    public static void main(String[] args) {//主方法
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String str = scanner.next();
            TreeNode root = stringToBinaryTree(str);
            inOrder(root);
            System.out.println();
        }
    }
    public static TreeNode stringToBinaryTree(String str){
        char curChar = str.charAt(index);
        if (curChar == '#'){//传入的树判空
            return null;
        }
        //最妙的来了读取的数据中序遍历，根左右
        TreeNode root = new TreeNode(curChar);//第一个进去之后就是根，因为读入的数据是先序遍历；

        index++;//根处理了，处理左子树
        root.left = stringToBinaryTree(str);//处理左子树这个方法太妙了。index是全局变量

        index++;
        root.right = stringToBinaryTree(str);

        return root;
    }
    public static void inOrder(TreeNode root){//中序输出
        if (root == null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val);
        System.out.print(" ");
        inOrder(root.right);

    }

}

